package com.zhanghp.class010;

import com.zhanghp.common.ListNode;

/**
 * 将两个升序链表合并为一个新的 升序 链表并返回
 * 新链表是通过拼接给定的两个链表的所有节点组成的
 * 测试链接 : https://leetcode.cn/problems/merge-two-sorted-lists/
 * @author zhanghp
 * @since 2024/2/21 11:47
 */
public class MergeTwoLists {

    static class Solution{
        public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
            if (head1 == null) {
                return head2;
            }
            if (head2 == null) {
                return head1;
            }
            ListNode head = head1.val > head2.val ? head2 : head1;
            ListNode cur1 = head.next;
            ListNode cur2 = head == head1 ? head2 : head1;
            ListNode temp = head;
            while (cur1 != null && cur2 != null) {
                if (cur1.val < cur2.val) {
                    temp.next = cur1;
                    cur1 = cur1.next;
                }else {
                    temp.next = cur2;
                    cur2 = cur2.next;
                }
                temp = temp.next;
            }
            temp.next = cur1 != null ? cur1 : cur2;
            return head;
        }
    }
}
